/*
 * Hierarchy.java
 *
 * Created on 9 November 2003, 00:52
 *
 * Copyright 2008 the Desert Labs Project (http://desertlabs.us)
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package us.desertlabs.collections;

import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

/**
 * This class allows groups of objects to be stored based on associated levels.
 * Levels are specified by integer values, and any given level can have an
 * arbitrary number of objects associated with it. Methods are provided that can
 * find the highest and lowest occurrences of object instances, were "highness"
 * refers to the value of the integer representing the level. All of the public
 * methods of <CODE>Hierarchy</CODE> are synchronized.
 *
 * @param <E> the datatype of the stored objects
 * @author Brandon Franklin
 */
public class Hierarchy<E> {

    /** The <CODE>Map</CODE> of data, grouped by level in the <CODE>Hierarchy</CODE> */
    final private Map<Integer, Set<E>> levels;

    /**
     * Creates a new instance of <CODE>Hierarchy</CODE>.
     */
    public Hierarchy() {
        levels = new TreeMap<Integer, Set<E>>();
    }

    /**
     * Adds a new object at the supplied level of the <CODE>Hierarchy</CODE>.
     *
     * @param level the level of the <CODE>Hierarchy</CODE> at which to add
     *        the new object
     * @param obj the object to be added
     * @throws IllegalArgumentException if the supplied object is null
     */
    public void add( final int level, final E obj ) {

        if( obj == null ) {
            throw new IllegalArgumentException( "Null objects cannot be stored in a Hierarchy." );
        }

        ensureStorageForLevel( level );
        final Set<E> setAtLevel = levels.get( level );
        setAtLevel.add( obj );
    }

    /**
     * Returns whether or not the <CODE>Hierarchy</CODE> contains the supplied
     * object at any level.
     *
     * @param obj the object to look for
     * @return whether or not the <CODE>Hierarchy</CODE> contains the supplied
     *         object at any level
     * @throws IllegalArgumentException if the supplied object is null
     */
    public boolean contains( final E obj ) {

        final int foundAt = findLowestOccurrence( obj );
        boolean found = true;

        if( foundAt == Integer.MAX_VALUE ) {
            found = false;
        }

        return found;
    }

    /**
     * Returns whether or not the <CODE>Hierarchy</CODE> contains the supplied
     * object at the specified level.
     *
     * @param level the level at which to look for the object
     * @param obj the object to look for
     * @return whether or not the <CODE>Hierarchy</CODE> contains the supplied
     *         object at the specified level
     * @throws IllegalArgumentException if the supplied object is null
     */
    public boolean contains( final int level, final E obj ) {

        if( obj == null ) {
            throw new IllegalArgumentException( "Null objects cannot be stored in a Hierarchy." );
        }

        final Set<E> setAtLevel = getAll( level );
        if( setAtLevel != null ) {
            return setAtLevel.contains( obj );

        }

        return false;
    }

    /**
     * Returns the highest level at which the supplied object could be found in
     * the <CODE>Hierarchy</CODE>, or <CODE>Integer.MIN_VALUE</CODE> if it
     * could not be found at all.
     *
     * @param obj the object to look for
     * @return the highest level at which the supplied object could be found in
     *         the <CODE>Hierarchy</CODE>, or <CODE>Integer.MIN_VALUE</CODE>
     *         if it could not be found at all
     * @throws IllegalArgumentException if the supplied object is null
     */
    public int findHighestOccurrence( final E obj ) {
        final Integer[] levelInts = levels.keySet().toArray( new Integer[levels.size()] );

        int foundAt = Integer.MIN_VALUE;
        for( int i = levelInts.length - 1; i >= 0; i-- ) {
            final int levelInt = levelInts[i].intValue();
            if( contains( levelInt, obj ) ) {
                foundAt = levelInt;
                break;
            }
        }

        return foundAt;
    }

    /**
     * Returns the lowest level at which the supplied object could be found in
     * the <CODE>Hierarchy</CODE>, or <CODE>Integer.MAX_VALUE</CODE> if it
     * could not be found at all.
     *
     * @param obj the object to look for
     * @return the lowest level at which the supplied object could be found in
     *         the <CODE>Hierarchy</CODE>, or <CODE>Integer.MAX_VALUE</CODE>
     *         if it could not be found at all
     * @throws IllegalArgumentException if the supplied object is null
     */
    public int findLowestOccurrence( final E obj ) {
        final Integer[] levelInts = levels.keySet().toArray( new Integer[levels.size()] );

        int foundAt = Integer.MAX_VALUE;
        for( final Integer element : levelInts ) {
            final int levelInt = element.intValue();
            if( contains( levelInt, obj ) ) {
                foundAt = levelInt;
                break;
            }
        }

        return foundAt;
    }

    /**
     * Returns the <CODE>Set</CODE> containing all objects at the requested
     * level of the <CODE>Hierarchy</CODE>, sorted in the order in which they
     * were added. If the result is null, then no such level has ever been used
     * in the <CODE>Hierarchy</CODE> instance.
     *
     * @param level the level of the <CODE>Hierarchy</CODE> from which to
     *        return the <CODE>Set</CODE>
     * @return the <CODE>Set</CODE> containing all objects at the requested
     *         level of the <CODE>Hierarchy</CODE>
     */
    public Set<E> getAll( final int level ) {
        return levels.get( level );
    }

    /**
     * Returns the number of levels that exist in the <CODE>Hierarchy</CODE>.
     *
     * @return the number of levels that exist in the <CODE>Hierarchy</CODE>
     */
    public int levels() {
        return levels.size();
    }

    /**
     * Removes an object from the supplied level of the <CODE>Hierarchy</CODE>.
     *
     * @param level the level of the <CODE>Hierarchy</CODE> from which to
     *        remove the object
     * @param obj the object to be removed
     * @return true if the object was found and removed, false if it could not
     *         be found and therefore was not removed
     * @throws IllegalArgumentException if the supplied object is null
     */
    public boolean remove( final int level, final E obj ) {

        if( obj == null ) {
            throw new IllegalArgumentException( "Null objects cannot be stored in a Hierarchy." );
        }

        final Set<E> setAtLevel = getAll( level );
        if( setAtLevel != null ) {
            return setAtLevel.remove( obj );
        }

        return false;
    }

    /**
     * Ensures that there is storage available for objects at the supplied level
     * of the <CODE>Hierarchy</CODE>.
     *
     * @param level the level in the <CODE>Hierarchy</CODE> to ensure that
     *        storage is available for
     */
    private void ensureStorageForLevel( final int level ) {
        Set<E> storage = levels.get( level );
        if( storage == null ) {
            storage = new LinkedHashSet<E>();
            levels.put( level, storage );
        }
    }
}
